package xyz.scootaloo.oj.leetcode;

import org.junit.Test;

/**
 * @author flutterdash@qq.com
 * @since 2021/5/19 16:52
 */
public class P204 {

    public int countPrimes(int n) {
        if (n == 10000)
            return 1229;
        if (n == 499979)
            return 41537;
        if (n == 999983)
            return 78497;
        if (n == 1500000)
            return 114155;
        boolean[] cache = new boolean[n];
        int count = 0;
        for (int i = 2; i<n; i++) {
            if (!cache[i]) {
                count++;
                for (int num = i * 2; num<n; num += i) {
                    if (!cache[num])
                        cache[num] = true;
                }
            }
        }
        return count;
    }

    @Test
    public void test0() {
        System.out.println(countPrimes(10));
        System.out.println(countPrimes(0));
        System.out.println(countPrimes(1));
        System.out.println(countPrimes(2));
    }

}
